/*
*

	*

给你一个数组 routes ，表示一系列公交线路，其中每个 routes[i] 表示一条公交线路，第 i 辆公交车将会在上面循环行驶。

例如，路线 routes[0] = [1, 5, 7] 表示第 0 辆公交车会一直按序列 1 -> 5 -> 7 -> 1 -> 5 -> 7 -> 1 -> ... 这样的车站路线行驶。
现在从 source 车站出发（初始时不在公交车上），要前往 target 车站。 期间仅可乘坐公交车。

求出 最少乘坐的公交车数量 。如果不可能到达终点车站，返回 -1 。

示例 1：

输入：routes = [[1,2,7],[3,6,7]], source = 1, target = 6
输出：2
解释：最优策略是先乘坐第一辆公交车到达车站 7 , 然后换乘第二辆公交车到车站 6 。
示例 2：

输入：routes = [[7,12],[4,5,15],[6],[15,19],[9,12,13]], source = 15, target = 12
输出：-1

提示：

1 <= routes.length <= 500.
1 <= routes[i].length <= 105
routes[i] 中的所有值 互不相同
sum(routes[i].length) <= 105
0 <= routes[i][j] < 106
0 <= source, target < 106

  - @author ala
  - @date 2024-09-17 21:32
*/
package main

import "fmt"

func main() {
	//routes := [][]int{{1, 2, 7}, {3, 6, 7}}
	//source, target := 1, 6

	routes := [][]int{{7, 12}, {4, 5, 15}, {6}, {15, 19}, {9, 12, 13}}
	source, target := 15, 12

	fmt.Println(numBusesToDestination(routes, source, target))
}

func numBusesToDestination(routes [][]int, source int, target int) int {
	return V1(routes, source, target)
}

/**
 *	1）找到途径每个站点的所有公交车，没辆公交车的所有站点
 *	2）bfs，返回深度
 *		从roots出发，找到途径roots的所有公交车，这些公交车的所有站点作为nexts
 *		以公交车为vis，而不是站点（否则超时，别问我咋知道的。。。）
 */
func V1(routes [][]int, source int, target int) int {
	sbm := make(map[int][]int)
	bsm := make(map[int][]int)
	mx := 0
	//	每个站点途径的公交车，每个公交车途径的站点
	for i := 0; i < len(routes); i++ {
		for _, r := range routes[i] {
			sbm[r] = append(sbm[r], i)
			bsm[i] = append(bsm[i], r)
			mx = max(mx, r)
		}
	}

	//	bfs求深度
	roots := []int{source}
	vis := make([]bool, len(routes))
	return bfs(sbm, bsm, 0, roots, target, vis, mx)
}

func bfs(sbm map[int][]int, bsm map[int][]int, depth int, roots []int, target int, vis []bool, mx int) int {
	nexts := make([]int, 0, 64)
	for _, r := range roots {
		if r == target {
			return depth
		}

		bs := sbm[r]
		_vis := make(map[int]bool)
		for _, b := range bs {
			//	用公交车做vis，如果用公交站会超时
			if vis[b] {
				continue
			}
			vis[b] = true
			for _, s := range bsm[b] {
				if _vis[s] {
					continue
				}
				_vis[s] = true
				nexts = append(nexts, s)
			}
		}
	}

	if len(nexts) == 0 {
		return -1
	} else {
		return bfs(sbm, bsm, depth+1, nexts, target, vis, mx)
	}
}
